\section{Introduction}

XML is a popular data representation, storing and exchanging language widely
used in many areas, such as in database systems and web services.
XPath\footnote{\url{https://www.w3.org/TR/xpath/}} and
XQuery\footnote{\url{https://www.w3.org/TR/xquery/}} are used for navigating
through elements of XML documents. The execution time of these queries come to
matter in processing of very large XML documents. Even though common query
processors on commodity computers suffice for evaluating queries over
commonplace documents, they do not suffice for doing over very large XML
documents such as a DBLP\footnote{\url{http://dblp.uni-trier.de/}} document dump
of 1.8 GB and an UniProtKB\footnote{\url{http://www.uniprot.org/help/uniprotkb}}
document of 358 GB. The current XML processing techniques enable us to evaluate
some queries efficiently. For example, a technique \cite{QiYD07} for extracting
parent-child and ancestor-descendant relationships is efficient because it uses
indices regardless of the order of results. However, due to the intrinsic nature
that the elements of an XML document are ordered, order-aware queries that contain 
axes such as \texttt{following}, \texttt{following-sibling}, \texttt{preceding},
\texttt{preceding-sibling} axes and \texttt{position} function are important.
Backward queries such as \texttt{parent} and \texttt{ancestor} axes used for
tracking back toward the root of the XML documents are also important. Some
algorithms such as structural join \cite{AlJYK02} use a join algorithm on two
lists ($\mathrm{AList}$ for ancestors and $\mathrm{DList}$ for descendants) to
determine child-parent and ancestor-descendant relationships. However, it takes
$\mathrm{O}((|\mathrm{AList}| + |\mathrm{DList}|)^2)$ time in the worst case.
Thus, it will take terrible time in processing very large documents. Besides,
predicates, which are an construct for filtering elements, are useful for
queries, while queries efficient evaluation of predicate-containing queries also
becomes an issue.

In this study, we aim at good absolute time, which is the shortest time for
processing a certain amount of data, of evaluating over large XML documents,
XPath queries including three classes: backward, order-aware and
predicate-containing queries. We propose a novel compact representation for
partial trees~\cite{HaMa16}, which is a data structure dedicated to processing
large XML documents on multiple computers. This representation consists of two
index sets: one accelerates extracting relationships between nodes; the other
enables us to avoid evaluating uninvolved nodes. With this two index sets, we
can process very large XML documents efficiently.
Our contributions are summarized as the follows:
\begin{itemize}
	\item We have proposed a compact tree representation that can be used for 
	efficiently process the three classes of XPath queries.
	\item Our prototype implementation have outperformed 
	BaseX\footnote{\url{http://basex.org/}} and achieved good absolute evaluation time. 
\end{itemize}
The experiments were conducted on Amazon Elastic Compute
Cloud\footnote{\url{https://aws.amazon.com/ec2/}} (EC2) cloud server, which is a
web service and provides flexible compute capacity in the cloud. The experiment
results show that our approach outperforms a start-of-the-art XML database BaseX
in better absolute time. The execution time over 358 GB of XML data is only
seconds averagely.

Figure \ref{fig:grammar} shows the syntax of our target subset of XPath. Our
prototype implementation accepts nested predicates, which means the location
steps inside a predicate can still have predicates, making queries in this study
more expressive. For the \texttt{position()} function, only \texttt{child} axis
is supported. 


The rest of this paper is organized in the following: 
Section 2 introduces our previous work: partial trees.
Section 3 presents the novel compact representation.  
Section 4 shows the querying algorithms used in the experiments.
Section 5 reports results and analysis.
Section 6 concludes the paper and show the future work. 


\begin{figure}\small
	\centering\fbox{
		\begin{minipage}{.9\linewidth}
			\textit{Query} ::= `\texttt{/}' \textit{LocationPath} \\
			\textit{LocationPath} ::= \textit{Step} $~|~$ \textit{Step} `\texttt{/}' \textit{LocationPath} \\
			\textit{Step} ::=  \textit{NameTest} \textit{Predicate}?      $~|~$   
			\textit{NameTest} [\textit{integer}]     \\
			\phantom{\textit{Step} ::}	  $~|~$ `/'\textit{NameTest} \textit{Predicate}?  $~|~$
			\textit{Axis::NameTest} \textit{Predicate}?      \\
			\textit{AxisName} ::=  `\texttt{child}' $~|~$ `\texttt{parent}'   
			$~|~$ `\texttt{descendant}'   $~|~$ `\texttt{ancestor}'  \\ 
			\phantom{\textit{Step} :}  $~|~$  `\texttt{descendant-or-self}' 
			$~|~$ `\texttt{ancestor-or-self}'  $~|~$ `\texttt{following}'    \\
			\phantom{\textit{Step} :}        $~|~$ `\texttt{following-sibling}'  
			$~|~$ `\texttt{preceding}  $~|~$ `\texttt{preceding-sibling}'  \\
			\textit{NameTest} ::= `\texttt{*}' $~|~$ \textit{string}  \\
			\textit{Predicate} ::= `\texttt{[}' ( \textit{LocationPath}   
			$~|~$   \textit{position}() = \textit{integer} ) `\texttt{]}'  
		\end{minipage}
	}
	\caption{Grammar of our target subset of XPath.}
	\label{fig:grammar}
\end{figure}

%  LocalWords:  XPath XQuery DBLP UniProtKB AList DList uninvolved
%  LocalWords:  BaseX LocationPath NameTest AxisName
